DSA-01 note

Array as Memory Block in C/C++

(1)acess:
data getByIndex(index)
insertByIndex(index, data)

(2)maintenance:

• construct(length)
• updateByIndex(Index, data)
  removeByIndex(index)

desired property : fast computation of address from index
=> fast random access

implicit assumption:
index to address done by formula

C++ STL Vector : a Growing array

get, update
STL vector : a more "structured" way of using arrays

!!STL

2-D array

access:
index = (row, col)
data getByIndex(Index)
address = arr + sizeof(data)x(row x nCol + cool)

maintenance:
length = (nRow, nCol)
construction(length)
arr=new data [nRow x nCol]

implementation
(1)one-block:tradeoff & succinct
(2)array of array: easier for programmers

Ordered array

想像有連續放東西：排好的值(ordered Value)
insert
update

Asymptotic Notation

goal : tough rather than steps
f(n)
g(n)